package com.dkd.day20250726;

import java.util.Arrays;
import java.util.Scanner;

public class Main35 {
    public static void main(String[] args) {
        //题目描述
        //现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N，接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间假设光纤的成本各不相同，且有些节点之间已经存在光纤相连。
        //
        //请你设计算法，计算出能联通这些基站的最小成本是多少。
        //
        //注意：基站的联通具有传递性，比如基站A与基站B架设了光纤，基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通。
        //
        //输入描述
        //第一行输入表示基站的个数N，其中：
        //
        //0 < N ≤ 20
        //第二行输入表示具备光纤直连条件的基站对的数目M，其中：
        //
        //0 < M < N * (N - 1) / 2
        //从第三行开始连续输入M行数据，格式为
        //
        //X Y Z P
        //
        //其中：
        //
        //X，Y 表示基站的编号
        //
        //0 < X ≤ N
        //0 < Y ≤ N
        //X ≠ Y
        //Z 表示在 X、Y之间架设光纤的成本
        //
        //0 < Z < 100
        //P 表示是否已存在光纤连接，0 表示未连接，1表示已连接
        //
        //输出描述
        //如果给定条件，可以建设成功互联互通的5G网络，则输出最小的建设成本
        //
        //如果给定条件，无法建设成功互联互通的5G网络，则输出 -1

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int [][] graph = new int[N+1][N+1];
        Arrays.stream(graph).forEach(graph1 -> Arrays.fill(graph1, Integer.MAX_VALUE));

            for (int j = 0; j < M; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int z = sc.nextInt();
                int p = sc.nextInt();

                if(p==0){
                    graph[x][y] = z;
                    graph[y][x] = z;
                }else{
                    graph[x][y] = 0;
                    graph[y][x] = 0;
                }

        }


            int answer= solve(graph,N);
        System.out.println(answer);
    }

    public static int solve(int [][] graph,int n){
        //准备，结果，判断是否存在，添加节点数量，最短距离。
        int min = 0;

        boolean[] visited = new boolean[n+1];

        visited[1] = true;
        int count = 1;


        int [] mindistance = new int[n+1];
        for(int i = 1; i <= n; i++){
            mindistance[i] = graph[1][i];
        }

        while(count<n){
            int minDis = Integer.MAX_VALUE;
            int index = 0;

            for(int i = 1; i <= n; i++){
                if(!visited[i] && mindistance[i] < minDis){
                    minDis = mindistance[i];
                    index = i;
                }
            }

            if(index == 0){
                return -1;
            }

            min += mindistance[index];
            visited[index] = true;
            count++;

            for(int i = 1; i <= n; i++){
                if(!visited[i] && graph[index][i] < mindistance[i]){
                    mindistance[i] = graph[index][i];
                }
            }



        }

        return min;
    }
}
